package com.czk.algorithm.binarySearchWithoutRecursive;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 非递归的二分查找法
 *
 * @Author:ChenZhangKun
 * @Date: 2020/7/25 12:02
 */
public class BinarySearchWithoutRecursive {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int i = binarySearch(7, arr);
        System.out.println(i);
    }

    public static int binarySearch(int target, int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    @Test
    public void binarySearchTest() {
        // 定义数组
        int[] arr = {4, 89, 5, 6, 1, 8, 3, 9, 7};
        // 排序
        Arrays.sort(arr);
        // 指定长度
        int left = 0;
        int right = arr.length - 1;
        // 循环
        while (left < right) {
            int mid = (left + right) / 2;
            // 拿到索引
            if (arr[mid] == 8) {
                System.out.println(mid);
                return;
            } else if (arr[mid] > 8) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println("没找到");
    }
}
